# Algorithms to filter result from couchdb views
# Its basically a binary search that when finds one result opens as a fan ;)

def binarySearch(viewResult, time):
    # return the index of the first time similar to the given time found in the list 
    # similar means that starts with!
    # return -1 if not found
    return _binarySearch(viewResult, time, 0, len(viewResult), len(viewResult))
    
def _binarySearch(viewResult, time, min, max, length):
    # utility function for binary search
    if(max<min):
        return -1
    mid = int((max+min)/2)
    if(mid<0 or mid>=length):
        return -1;
    midTime = viewResult[mid].key
    if(midTime.startswith(time)):
        return mid
    # couchdb has dates sorted from most recent to oldest
    elif(midTime[0:len(time)]<time): 
        return _binarySearch(viewResult, time, mid+1, max, length)
    else:
        return _binarySearch(viewResult, time, min, mid-1, length)        
    
def fanSearch(viewResult, time):
    # the fan search algorithm
    start = int(binarySearch(viewResult, time))
    print start
    if start==-1:
        return []
    else:
        result = [viewResult[start].value]
        low = start-1
        high = start+1
        finishLow = False
        finishHigh = False
        while (low>=0 and high<len(viewResult)):
            # exit loop if no more elements with given time found
            if finishHigh and finishLow:
                break
            # check lower values
            if(low>=0 and viewResult[low].key.startswith(time)):
                result.insert(0, viewResult[low].value)
                low -= 1
            else:
                finishLow = True
            # check higher values
            if(high<len(viewResult) and viewResult[high].key.startswith(time)):
                result.append(viewResult[high].value)
                high += 1
            else:
                finishHigh = True
    return result      